#define _CRT_SECURE_NO_WARNINGS 1


void Swap(int* p1, int* p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
 struct ListNode 
 {
 	int val;
 	struct ListNode *next;
  };
 
#include<stdio.h>

 struct ListNode* _MergeSort(struct ListNode* head, struct ListNode** pphead)
{
    if (head->next == NULL)
    {
        return head;
    }

    struct ListNode* slow = head;
    struct ListNode* fast = head;
    struct ListNode* sprev= NULL;
    while (fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        sprev = slow;
        slow = slow->next;
    }
    struct ListNode* newhead = slow;
    sprev->next = NULL;

     head = _MergeSort(head, pphead);
     newhead = _MergeSort(newhead, pphead);
    struct ListNode* plist = (*pphead);
    while (head != NULL && newhead != NULL)
    {
        if (head->val > newhead->val)
        {
            plist->next = newhead;
            newhead = newhead->next;
        }
        else
        {
            plist->next = head;
            head = head->next;
        }
        plist = plist->next;
    }

    if (newhead != NULL)
    {
        plist->next = newhead;
    }
    
    if(head!= NULL)
    {
        plist->next = head;
    }
    return (*pphead)->next;
}

struct ListNode* CreateNode(int val)
{
    struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newnode->val = val;
    newnode->next = NULL;

    return newnode;
}
struct ListNode* sortInList(struct ListNode* head)
{
    if (head == NULL)
    {
        return NULL;
    }

    struct ListNode* plist = CreateNode(0);
    _MergeSort(head, &plist);

    return plist->next;
    // write code here
}
int main()
{
    /// <summary>
    /// [-426572,-406609,724427,-157789,-132713,720732,-39078,-348926,-693458,559374,114739,-748249,428207,-767407,401563,646432,-682870,483610,-608888,94840,749542,359115,131739,935294,347325,80573,-869091,-757897,-860166,-227942,-484068,-170790,-362441,-860466,819197,817675,886101,463504,-100482,496406,-860791]
    /// </summary>
    /// <returns></returns>
    struct ListNode* l1 = CreateNode(-428572);
    struct ListNode* l2 = CreateNode(-406609);
    struct ListNode* l3 = CreateNode(724427);
    struct ListNode* l4 = CreateNode(-157789);
    struct ListNode* l5 = CreateNode(-132713);

    l1->next = l2;
    l2->next = l3;
    l3->next = l4;
    l4->next = l5;

    struct ListNode* head = sortInList(l1);
	return 0;
}